Field of the Invention
The invention relates to a method for executing individual algorithms using a reconfigurable circuit, and to an apparatus for carrying out such a method.
The size and hence resources of reconfigurable circuits are limited. Often, the resources of such a circuit are not sufficient to execute two or more algorithms at the same time or one individual, relatively large algorithm.
A relatively large algorithm, which requires more resources than are available in the reconfigurable circuit and which needs to be executed using this circuit alone, is generally broken down into a plurality of subalgorithms, each of which itself represents a respective algorithm in turn and is chosen such that the circuit has sufficient resources for executing this subalgorithm.
These subalgorithms are executed in the circuit successively in time such that each of these subalgorithms is executed using the circuit which is configured for this subalgorithm and that, after execution of one subalgorithm, a succeeding subalgorithm is executed, the circuit being reconfigured for this succeeding subalgorithm after execution of this one subalgorithm, in so far as this succeeding subalgorithm is different from this one subalgorithm.
Data-dependent branch operations mean that it is not until at the time of execution, i.e. during the actual execution or processing of the larger algorithm, that it is known which of these subalgorithms of the larger algorithm is actually needed. At the compile time, i.e. before the time of execution, there is no indication available of which subalgorithms and hence configurations of the circuit are actually needed.
One way of still executing the larger algorithm using the reconfigurable circuit which has too few resources for this purpose is to configure this circuit individually for all subalgorithms of the larger algorithm in succession, for example on the basis of a prescribed program flow. In this context, only the configured subalgorithms which are needed are executed. If a subalgorithm is not needed, the configuration for this subalgorithm is erased without executing this subalgorithm.
Configuring the circuit during the time of execution for an unneeded part of the larger algorithm costs valuable execution time. A method is therefore required which recognizes and loads the necessary configurations in good time during execution.
M. Vasilko and Djamel Ait-Boudaoud: xe2x80x9cArchitectural Synthesis Techniques for Dynamically Reconfigurable Logicxe2x80x9d in Reiner W. Hartenstein, Manfred Glesner (Eds.): xe2x80x9cField-Programmable Logic, Smart Applications, New Paradigms and Compilersxe2x80x9d, 6th Int""l Workshop on Field-Programmable Logic and Applications, FPL ""96, Darmstadt, Germany, Sep. 23-25, 1996, Proceedings, Springer-Verlag, pp. 290-296 discloses the practice of calculating for the compile time the order on the basis of which the individual subalgorithms of a larger algorithm are configured in a circuit. In this case, a reconfiguration controller is obtained in which the sequence on the basis of which the subalgorithms are configured is fixed. In this case, the result of a branch operation is required in order to determine the correct subalgorithm which is to be configured.
The object of the present invention is to provide a method of processing individual algorithms with a reconfigurable circuit and an apparatus for carrying out the method which overcome the above-noted deficiencies and disadvantages of the prior art devices and methods of this general kind, and which further enable shortening the execution time in a method for executing individual algorithms using the reconfigurable circuit which has sufficient resources for executing each individual algorithm, and in which the algorithms which are to be executed are configured and executed in the circuit successively in time.
With the above and other objects in view there is provided, in accordance with the invention, a method of executing individual algorithms, which comprises:
providing a reconfigurable circuit with sufficient resources for executing each individual algorithm of a plurality of algorithms, and executing a plurality of algorithms in the circuit successively in time; and
during execution of a given algorithm, reconfiguring the circuit for a following algorithm so far as the following algorithm is different from the given algorithm currently being executed.
On the basis of this solution, each algorithm is executed using the circuit which is configured for this algorithm, and, during execution of one algorithm, a succeeding algorithm is executed, the circuit being reconfigured for this succeeding algorithm during actual execution of this one algorithm, at least in so far as this succeeding algorithm is different from this one algorithm.
On this basis, the following algorithm is advantageously configured in the circuit during the actual time of execution of an algorithm and may, under some circumstances, start to operate during the actual time of execution of the one algorithm. However, a prerequisite for this is a circuit which can be dynamically configured in such a manner. Suitable circuits for this are particular products from the company Xilinx, e.g. the chip XC62xx, which already afford the basic opportunities for such dynamic configuration. The chips can be configured in the same way as writing to a memory. A configuration memory cell is addressed and then has information written to it. Accordingly, the chip can be configured during the time of execution.
With the above and other objects in view there is also provided, in accordance with an alternative mode, a method of executing individual algorithms, which comprises:
providing a reconfigurable circuit with sufficient resources for executing each individual algorithm of a plurality of algorithms, and executing a plurality of algorithms in the circuit successively in time;
reconfiguring the circuit for a following algorithm during and/or after execution of a given algorithm, at least in so far as the following algorithm to be executed is different from the given algorithm; and
if a variety algorithms may need to be executed after execution of the given algorithm, reconfiguring the circuit for a following algorithm having a greatest probability of requiring execution after the given algorithm.
On the basis of this solution, each algorithm is executed using the circuit which is configured for this algorithm, and, during and/or after execution of one algorithm, a succeeding algorithm is executed, the circuit being reconfigured for this succeeding algorithm during and/or after execution of this one algorithm, at least in so far as this succeeding algorithm is different from this one algorithm, where at least one particular algorithm has at least two associated algorithms, each of which has a respectively different particular probability of being suitable for being executed as succeeding algorithm during and/or after execution of this particular algorithm, and where, of these associated algorithms, the one which is actually executed as the succeeding algorithm is the one which has the greatest probability.
Unlike the known method specified above, in which the order of configuration of the individual sub-algorithms of a larger algorithm is calculated for the compile time, and which is a static method, this method has the advantage that it is possible to infer an algorithm which is to be executed as succeeding algorithm for a particular algorithm earlier, which increases the parallelism between configuration and calculation, and hence the system performance, in particular reduces the execution time.
In this method, the circuit can be configured for a succeeding algorithm after execution of an algorithm, and/or it can be configured for a succeeding algorithm during execution of an algorithm, i.e. can be configured dynamically.
Irrespective of whether a circuit is configured for the succeeding algorithm after or during execution of an algorithm, this method is itself a dynamic method, since the succeeding algorithm is not fixed, but rather is determined on the basis of a probability.
In the second method, the dynamic configuration of the circuit can contribute to further shortening of the execution time, as compared to the first above-outlined method.
In the second method, the fundamental features are the prerequisite that at least one particular algorithm has at least two associated algorithms, each of which has a respectively different particular probability of being suitable for being executed as succeeding algorithm during and/or after execution of this particular algorithm, and that, of these associated algorithms, the one which is actually executed as the succeeding algorithm is the one which has the greatest probability. This means that the probability for each of these associated algorithms does not have to be the same for all of these algorithms, and that, among these algorithms, there is an individual algorithm with a relatively greatest probability.
The different probabilities of the various associated algorithms need to be known as additional information in this method. Without this additional information, with two algorithms which are each associated with a particular algorithm, the probability of being executed as succeeding algorithm during and/or after execution of this particular algorithm is 50% in each case, which means that a reliable decision cannot be made without this information.
To obtain the additional information, the preferable and advantageous procedure is to ascertain for each algorithm which is associated with a particular algorithm and is suitable for being executed as succeeding algorithm during and/or after execution of this particular algorithm how often in the past this one associated algorithm has been executed as a succeeding algorithm during and/or after execution of this particular algorithm as compared with each of the other associated algorithms, where that algorithm among the associated algorithms which has been executed comparatively most often in this past has the greatest probability of being executed as succeeding algorithm during and/or after the current execution of the particular algorithm.
In accordance with another feature of the invention, a restructuring of the circuit during execution of the given algorithm, for execution of the following algorithm to be executed, comprises reconfiguring those parts of the circuit which have been configured for execution of the given algorithm currently being executed.
In accordance with a further feature of the invention, the method comprises:
determining, for each algorithm that may need to be executed after a given algorithm, how often in the past the respective algorithm has been executed after execution of the given algorithm; and
reconfiguring the circuit for the algorithm having been executed most frequently in the past after execution of the given algorithm.
In accordance with again an added feature of the invention, each algorithm that may need to be executed after the given algorithm is assigned a number. The number
has a particular initial value;
is changed by a particular value if the algorithm having the associated number in question is executed after execution of the given algorithm; and
is changed by a particular other value if the algorithm having the associated number in question is not executed after execution of the given algorithm.
This method involves extrapolating into the future from decisions in the past. If a particular algorithm has, by way of example, two associated algorithms which are suitable for being executed as succeeding algorithm during and/or after execution of this particular algorithm, and if the one associated algorithm has been selected as succeeding algorithm more frequently in the recent past, then it can be assumed that this associated algorithm has a greater probability of being needed. This means that the incorrect decisions can be reduced by extrapolating into the future. In this context, probability is to be understood as meaning that it is a certainty that an associated algorithm occurs more frequently.
This method can advantageously be carried out such that each algorithm which is associated with a particular algorithm and is suitable for being executed as succeeding algorithm during and/or after execution of this particular algorithm is allocated a respective changing number which assumes an initial value which is the same for all these associated algorithms so long as this associated algorithm has not yet been executed as a succeeding algorithm for this particular algorithm, where the number of an associated algorithm is changed by a particular amount in the direction towards a particular extreme value, which is the same for all these associated algorithms, of this number if this associated algorithm is executed as succeeding algorithm for the particular algorithm, while at the same time the number of each other associated algorithm, which is not executed as succeeding algorithm for the particular algorithm, is changed by a particular amount in the direction away from the extreme value, where the associated algorithm whose number reaches the extreme value first has the greatest probability of being executed as succeeding algorithm during and/or after the current execution of the particular algorithm.
With the above and other objects in view there is also provided, in accordance with the invention, an apparatus for executing individual algorithms, comprising:
a reconfigurable circuit having sufficient resources for executing each individual algorithm of a plurality of algorithms;
wherein a plurality of algorithms are executed in the circuit successively in time; and
wherein, during an execution of a given algorithm, the circuit is reconfigured for a following algorithm so far as the following algorithm is different from the given algorithm currently being executed.
There is also provided xe2x80x94in the context of the second above-outlined method xe2x80x94an apparatus for executing individual algorithms, comprising:
a reconfigurable circuit having sufficient resources for executing each individual algorithm of a plurality of algorithms;
wherein a plurality of algorithms are executed in the circuit successively in time;
wherein the circuit is reconfigured for a following algorithm during and/or after execution of a given algorithm, at least in so far as the following algorithm to be executed is different from the given algorithm; and
wherein, if a variety algorithms may need to be executed after execution of the given algorithm, the circuit is reconfigured for a following algorithm having a greatest probability of requiring execution after the given algorithm.
In accordance with again another feature of the invention, a plurality of counters are provided for selectively counting up or down for changing the number.
In accordance with a concomitant feature of the invention, the counters increase the number only if the number is less than a particular maximum value, and they decrease the number only if the number is greater than a particular minimum value.
In the context of a preferred and advantageous apparatus for carrying out this method, therefore, each algorithm which is associated with a particular algorithm and is suitable for being executed as succeeding algorithm during and/or after execution of this particular algorithm has a respective associated up/down counter where, in each counter, a counter reading which represents the number of the counter""s associated algorithm is set to the initial value of this number so long as this associated algorithm has not yet been executed as a succeeding algorithm for the particular algorithm, where the counters are controlled such that
the counter reading of a counter is changed by the particular amount in the direction towards the particular extreme value of this counter reading if the associated algorithm of this counter is executed as succeeding algorithm for the particular algorithm, while at the same time the counter reading of each other counter, whose associated algorithm is not executed as succeeding algorithm for the particular algorithm, is changed by the particular amount in the direction away from the extreme value, where
the associated algorithm whose counter reaches the extreme value first has the greatest probability of being executed as succeeding algorithm during and/or after the current execution of the particular algorithm.
The invention advantageously permits a time saving for configuration in dynamically reconfigurable systems. For production, similar techniques to those for a branch prediction unit for processors can be applied.
Other features which are considered as characteristic for the invention are set forth in the appended claims.
Although the invention is illustrated and described herein as embodied in a method for executing individual algorithms using a reconfigurable circuit, and apparatus for carrying out such a method, it is nevertheless not intended to be limited to the details shown, since various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.